package org.liaohailong.helloworld.practice;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Author: liaohailong
 * Time: 2021/6/23 11:06
 * Describe: 初级算法 - 其他类型
 */
public class OtherPractice {

    // LC 位1的个数
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        return Integer.bitCount(n);
    }

    // LC 汉明距离
    public int hammingDistance(int x, int y) {
        int r = x ^ y;
        int total = 0;
        for (int i = 0; i < 32; i++) {
            if (((r >>> i) & 1) == 1) total++;
        }
        return total;
    }

    // LC 颠倒二进制位
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int res = 0;
        for (int i = 0; i < 32; i++) {
            int t = n & 1;
            res <<= 1;
            res += t;
            n >>= 1;
        }
        return res;
    }

    // LC 杨辉三角
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>(numRows);
        for (int i = 1; i <= numRows; i++) {
            int rowIndex = i - 1;
            List<Integer> list = new ArrayList<>();
            result.add(rowIndex, list);
            for (int j = 0; j < i; j++) {
                if (j == 0 || j == i - 1) {
                    // 边界为1
                    list.add(1);
                } else {
                    // 自身的值等于上一层的第j-1个元素加上第j个元素
                    int prevRowIndex = i - 2;
                    List<Integer> arrays = result.get(prevRowIndex);
                    Integer val1 = arrays.get(j - 1);
                    Integer val2 = arrays.get(j);
                    list.add(val1 + val2);
                }
            }
        }
        return result;
    }


    // LC 有效的括号
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            switch (c) {
                case '(':
                case '{':
                case '[':
                    stack.push(c);
                    break;
                case ')': {
                    if (stack.isEmpty()) return false;
                    char pop = stack.pop();
                    if (pop != '(') return false;
                }
                break;
                case ']': {
                    if (stack.isEmpty()) return false;
                    char pop = stack.pop();
                    if (pop != '[') return false;
                }
                break;
                case '}': {
                    if (stack.isEmpty()) return false;
                    char pop = stack.pop();
                    if (pop != '{') return false;
                }
                break;
            }
        }
        return stack.isEmpty();
    }

    // LC 缺失数字
//    public int missingNumber(int[] nums) {
//        Arrays.sort(nums);
//        int max = nums.length;
//
//        for (int i = 0; i < nums.length; i++) {
//            if (i == 0 && nums[i] != 0) return 0;
//            else if (i == nums.length - 1 && nums[i] != max) return max;
//            else {
//                if (nums[i + 1] - nums[i] > 1) return nums[i] + 1;
//            }
//        }
//        return 0;
//    }


    // LC 缺失数字
//    public int missingNumber(int[] nums) {
//        int max = nums.length;
//        HashSet<Integer> set = new HashSet<>();
//        for (int num : nums) set.add(num);
//        for (int i = 0; i <= max; i++) {
//            if (!set.contains(i)) return i;
//        }
//        return 0;
//    }

    // LC 缺失数字 - 求和
//    public int missingNumber(int[] nums) {
//        int max = nums.length;
//        int min = 1;
//        int total = ((min + max) * max) / 2;
//        for (int num : nums) total -= num;
//        return total;
//    }

    // LC 缺失数字
    public int missingNumber(int[] nums) {
        int xor = 0;
        for (int i = 0; i < nums.length; i++)
            xor ^= nums[i] ^ (i + 1);
        return xor;
    }
}
